#include "../include/brute_force.h"
#include <string.h>

/**
 * 计算给定物品组合的总重量
 * @param items 物品数组
 * @param n 物品数量
 * @param selected 物品选择状态数组
 * @return 总重量
 */
static double calculate_weight(Item* items, int n, int* selected) {
    double total_weight = 0;
    for (int i = 0; i < n; ++i) {
        if (selected[i]) {
            total_weight += items[i].weight;
        }
    }
    return total_weight;
}

/**
 * 计算给定物品组合的总价值
 * @param items 物品数组
 * @param n 物品数量
 * @param selected 物品选择状态数组
 * @return 总价值
 */
static double calculate_value(Item* items, int n, int* selected) {
    double total_value = 0;
    for (int i = 0; i < n; ++i) {
        if (selected[i]) {
            total_value += items[i].value;
        }
    }
    return total_value;
}

/**
 * 暴力求解0-1背包问题
 * 时间复杂度：O(2^n)，空间复杂度：O(n)
 * @param items 物品数组
 * @param n 物品数量
 * @param capacity 背包容量
 * @param result 结果结构体指针
 */
void brute_force_knapsack(Item* items, int n, int capacity, Result* result) {
    // 初始化结果
    result->total_value = 0;
    result->selected_count = 0;
    result->time_taken = 0;
    result->memory_used = 0;
    result->selected_items = NULL;

    // 记录开始时间
    clock_t start = clock();

    // 分配内存
    int* selected = (int*)calloc(n, sizeof(int));
    int* best_selected = (int*)calloc(n, sizeof(int));
    if (!selected || !best_selected) {
        printf("Memory allocation failed\n");
        free(selected);
        free(best_selected);
        return;
    }

    // 遍历所有可能的组合（2^n种）
    double best_value = 0;
    for (int i = 0; i < (1 << n); ++i) {
        // 生成当前组合
        for (int j = 0; j < n; ++j) {
            selected[j] = (i >> j) & 1;
        }

        // 计算当前组合的总重量和价值
        double current_weight = calculate_weight(items, n, selected);
        double current_value = calculate_value(items, n, selected);

        // 如果当前组合可行且价值更高，则更新最优解
        if (current_weight <= capacity && current_value > best_value) {
            best_value = current_value;
            memcpy(best_selected, selected, n * sizeof(int));
        }
    }

    // 记录结束时间和内存使用
    clock_t end = clock();
    result->time_taken = ((double)(end - start)) / CLOCKS_PER_SEC * 1000;
    result->memory_used = n * sizeof(int) * 2;  // selected和best_selected数组

    // 保存结果
    result->total_value = best_value;
    result->selected_items = (int*)malloc(n * sizeof(int));
    if (result->selected_items) {
        for (int i = 0; i < n; ++i) {
            if (best_selected[i]) {
                result->selected_items[result->selected_count++] = items[i].id;
            }
        }
    }

    // 释放内存
    free(selected);
    free(best_selected);
} 